﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定两个字符串s和p，找到s中所有p的异位词的⼦串，返回这些⼦串的起始索引。不考虑答案输出的顺序。
//异位词指由相同字⺟重排列形成的字符串（包括相同的字符串）。
//eg:输⼊ : s= cbaebabacd, p = abc  输出 : [0, 6]

#include <iostream>
using namespace std;

bool HashJudge(int* a1,int* a2)//判断两个哈希表是否一样
{
	for (int p=0; p < 26; p++)
	{
		if (a1[p] != a2[p])
			return false;
	}
	return true;
}

//思路：滑动窗口+哈希。转化为：寻找长度为三的p中相同元素构成的s的子数组
void findAnagrams(char* s,char* p,int szs,int szp)
{
	int counts[26] = { 0 }, countp[26] = { 0 };
	for (int i = 0; i < szp; i++)
	{
		countp[p[i] - 'a']++;//先统计目标字符的个数和种类
	}

	for (int left=0,right=0;right<szs;right++)
	{
		counts[s[right] - 'a']++;//进窗口
		while (right - left + 1 > szp)//判断
		{
			counts[s[left] - 'a']--;//出窗口
			left++;
		}
		if (right - left + 1&&HashJudge(counts, countp))//再判断两个表的元素种类个数是否一样
		{
			cout << left<<' ';//更新结果
		}
	}
	cout << endl;
}

int main()
{
	char s[] = "abcabcabcabc",p[] = "abc";
	cout << "s: " << s << "  p: " << p << endl;

	findAnagrams(s,p,strlen(s),strlen(p));

	return 0;
}